package interview.recursion;

import interview.common.Node;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description: 递归
 * User: xxm
 * Date: 2018-02-18
 * Time: 17:19
 */
public class LinkedListReverser {

    /**
     * 反转单链表
     *
     * @param head head the linked list to reverse
     * @return head of the reversed linked list
     */
    public Node reverseLinkedList(Node head) {

        if (head == null || head.getNext() == null) {
            return head;
        }

        // 反转除首元素节点外的其他节点
        Node newHead = reverseLinkedList(head.getNext());
        // 使第二个节点指向首元素节点
        head.getNext().setNext(head);
        // 首节点指向null
        head.setNext(null);
        return newHead;
    }

    public static void main(String[] args) {
        LinkedListCreator creator = new LinkedListCreator();
        LinkedListReverser reverser = new LinkedListReverser();

        Node.printLinkedList(reverser.reverseLinkedList(
                creator.createLinkedList(new ArrayList<Integer>())));

        Node.printLinkedList(reverser.reverseLinkedList(
                creator.createLinkedList(Arrays.asList(1)))
        );

        Node.printLinkedList(reverser.reverseLinkedList(
                creator.createLinkedList(Arrays.asList(1, 2, 3, 4, 5)))
        );
    }
}
